package LimitedTimeGame.Day_0215;

/**
 * @author zxc
 * @date 2023/02/15 15:11
 **/

import java.util.Arrays;
import java.util.Stack;

/**
 * 题目 : 回文素数
 * 题目详述 ：
 * 求出大于或等于N的最小回文素数。
 * 回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数。
 * 例如，2，3，5，7，11 以及13 是素数。
 * 回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是回文数。
 * 例如，12321 是回文数。
 *
 * 提示：
 * 1 <= N <= 10^8
 * 答案肯定存在，且小于 2 * 10^8。
 *
 */
public class PrimePalindrome02 {
    /**
     * 思路 ：
     * 即，由于引入的参数n，是让我们去求解大于等于n的最小回文素数;
     * 若是遍历所有大于等于n的值，又由于n的取值范围[1 , 10^8]，所以遍历过多的数字，会导致超时情况;
     * ===>
     * 核心思想 ：在于优化回文数的查找，即不需要去遍历所有数字，而是优化遍历的对象。
     * ===》即，去遍历所有可能的回文数;
     * （1）假设当前传入的参数n（abcde/abcdef）
     * （2）其最小回文字符串 ：
     *  当传入参数长度为奇数时，即 abcba / abdba;
     *  当传入参数长度为偶数时，即 abccba / abddba;
     *  ===> 即，只需要对于所传入参数的前半部分进行逐步累积处理，直至找到合适值;
     *
     * @param n
     * @return
     */
    public int primePalindrome(int n) {
        while(true){
            // 获取大于等于n的下一个最小回文数
            n = getNextPalindrome(n);
            // 判断当前最小回文数是否为素数
            if(isPrime(n)){
                return n;
            }
            // 由于上述所找到的回文数不满足素数的条件，所以需要去寻找下一个最小的回文数;
            // ===> 即，由于当前n为回文数，将n++使得，其必然对于前半部分进行加一操作，获取新的最小回文数;
            n++;
        }
    }
    // 获取大于等于当前元素n的最小回文数;
    private int getNextPalindrome(int n) {
        char[] array = String.valueOf(n).toCharArray();
        int len = array.length;
        int mid = len / 2;
        // 重复寻找满足条件 ：长度 >= n的最小回文数
        while(true){
            // 大于等于n的最小回文串 ： 以当前元素n前半部分的元素为参照，翻转到后半部分元素;
            for(int i = 0 ; i < len ; i++){
                array[len - 1 - i] = array[i];
            }
            int minPalindrome = Integer.valueOf(new String(array));
            System.out.println(minPalindrome);
            // 若是前半部分翻转到后半部分所形成的最小回文串 >= n的话，则直接返回即可;
            if(minPalindrome >= n){
                return minPalindrome;
            }
            // 若是前半部分反转到后半部分形成的最小回文串 < n的话，则选择将前半部分 + 1;
            else {
                // 若是当前数字为奇数的话，则需要对于arr[mid]进行加一操作;
                // 若是当前数字为偶数的话，则需要对于arr[mid - 1]进行加一操作;
                int j = (len % 2 == 1) ? mid : mid - 1;
                // 进位操作
                while(array[j] == '9'){
                    array[j--] = '0';
                }
                array[j]++;
            }
        }
    }

    // 判断该数是否为质数/素数
    private boolean isPrime(int n) {
        if(n <= 5){
            return n == 2 || n == 3 || n == 5;
        }
        for(int i = 2 ; i <= (int)Math.sqrt(n) ; i++){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
}
